package leetcode.tree;

import java.util.HashMap;
import java.util.Map;

import datastructure.binarytree.TreeNode;

public class LeetCode106 {
    Map<Integer, Integer> inorderCache = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderCache.put(inorder[i], i);
        }
        return build(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    }

    TreeNode build(int[] postorder, int postlo, int posthi, int[] inorder, int inlo, int inhi) {
        if (postlo > posthi || inlo > inhi) {
            return null;
        }
        // 终止条件
        // 根节点值
        int rootVal = postorder[posthi];
        int rootValIndexInorder = inorderCache.getOrDefault(rootVal, -1);
        // 中序 [9,3,15,20,7]
        // 后序 [9,15,7,20,3]
        TreeNode root = new TreeNode(rootVal);
        int rightTreeSize = inhi - rootValIndexInorder;
        System.out.println(String.format("rootVal: %s, index:%s", rootVal, rootValIndexInorder));
        root.left = build(postorder, postlo, posthi - rightTreeSize - 1, inorder, inlo, rootValIndexInorder - 1);
        root.right = build(postorder, posthi - rightTreeSize, posthi - 1, inorder, rootValIndexInorder + 1, inhi);
        // 也可以用 左子树的大小做推断
        /**
         * int leftSize = index - inStart;
         * root.left = build(inorder, inStart, index - 1, postorder, postStart,
         * postStart + leftSize - 1);
         * root.right = build(inorder, index + 1, inEnd, postorder, postStart +
         * leftSize, postEnd - 1);
         */
        return root;
    }
}
